מבוא לגרפים:

• גרף $G=(V,E)$ מוגדר על ידי קבוצה סופית של קודקודים (Vertices - $V$) וקבוצת צלעות (Edges - $E$) שמייצגות קשרים בין זוגות קודקודים.
• גרפים משמשים למידול בעיות רבות במציאות, כגון כבישים וניווט, רשתות תקשורת, קשרים חברתיים ("לחיצות ידיים"), ואף מבנים ביולוגיים כמו קיפול חלבונים.

סוגי גרפים:

• גרף לא מכוון (Undirected Graph):
  • גרף בו הקשרים הם סימטריים.
  • הצלע מיוצגת כזוג לא סדור של קודקודים, ונהוג לסמנה כ-$(u,v)$.
  • לדוגמא: אנשים שלחצו ידיים במסיבה.
  • 
• גרף מכוון (Directed Graph):
  • גרף בו הקשרים הם חד-סטריים.
  • הצלע מיוצגת כזוג סדור מ-$u$ ל-$v$, כאשר $u$ נקרא המקור (Tail) ו-$v$ נקרא היעד (Head).
  • לדוגמה: כביש חד-סטרי או אדם שאמר שלום והשני לא ענה.
  • 

הגדרות ומושגי יסוד:

• גרף שלם (Complete Graph):
  • גרף לא מכוון שבו קיימת צלע בין כל זוג קודקודים (מספר הצלעות בו הוא ריבועי).
• שכנות (Adjacency):
  • בגרף לא מכוון, אם קיימת צלע $(u,v)$, אומרים שהקודקודים $u$ ו-$v$ הם שכנים (Adjacent).
• דרגה (Degree):
  • מספר הצלעות המחוברות לקודקוד.
  • בגרף מכוון נהוג להפריד לדרגה יוצאת (Out-degree) - מספר הצלעות שיוצאות מהקודקוד, ודרגה נכנסת (In-degree) - מספר הצלעות שנכנסות אליו.
• תת-גרף (Subgraph):
  • גרף $G^{\prime }=(V^{\prime },E^{\prime })$ המורכב מתת-קבוצה של קודקודים ($V^{\prime }\subseteq V$) ותת-קבוצה של צלעות ($E^{\prime }\subseteq E$) של הגרף המקורי, בתנאי שכל הצלעות ב-$E^{\prime }$ מחברות אך ורק קודקודים שנמצאים ב-$V^{\prime }$.
• מסלולים ומעגלים:
  • מסלול (Path): רצף של קודקודים שביניהם קיימות צלעות עוקבות. אורך המסלול מוגדר כמספר הצלעות בו (מספר הקודקודים פחות אחד).
  • מסלול פשוט (Simple Path): מסלול שבו מבקרים בכל קודקוד פעם אחת בלבד, פרט אולי לקודקוד הראשון והאחרון שיכולים להיות זהים.
  • מעגל (Cycle): מסלול שמתחיל ומסתיים בדיוק באותו הקודקוד.

קשירות (Connectivity):

• בגרף לא מכוון:
  • קודקודים $u$ ו-$v$ נחשבים קשירים אם קיים מסלול ביניהם.
  • הגרף כולו מוגדר כגרף קשיר אם קיים מסלול בין כל זוג קודקודים בגרף.
  • רכיב קשירות (Connected Component): קבוצה מקסימלית של קודקודים בגרף שכולם קשירים זה לזה.
• בגרף מכוון:
  • קודקודים $u$ ו-$v$ הם קשירים היטב (Strongly Connected) אם קיים מסלול מ-$u$ ל-$v$ וגם מסלול הפוך מ-$v$ ל-$u$.
  • רכיב קשירות היטב: קבוצה מקסימלית של קודקודים שקשירים היטב זה לזה.

עצים ויערות:

• עץ (Tree): גרף לא מכוון שהוא קשיר וחסר מעגלים.
• יער (Forest): גרף לא מכוון חסר מעגלים (למעשה, אוסף של עצים שיכולים להיות לא קשורים זה לזה).

ייצוג גרפים:

• ישנן שתי דרכים עיקריות לייצג גרף, כאשר לכל אחת מהשיטות יש יתרונות וחסרונות בהתאם לכמות הצלעות
• רשימת שכנויות (Adjacency lists):
  • מערך בגודל V, שבו כל תא מייצג קודקוד ומכיל רשימה מקושרת של כל השכנים שלו בגרף. בגרף לא מכוון, כל צלע תופיע פעמיים (פעם אחת בכל רשימה של כל קצה).
  • סיבוכיות מקום - Θ(V+E) :
    • כיוון שאנו שומרים מערך בגודל V וכל צלע מצריכה שמירת איבר ברשימה.
    • גישה זו עדיפה לגרפים דלילים שבהם כמות הצלעות רחוקה מ-$v^2$.
  • זמן מציאת כל השכנים של קודקוד:
    • הוא פורפוציונלי למספר השכנים שלו, משמע עבור קודקוד u נקבל $\mathrm{\Theta }(degree(u))$
  • בדיקת שכנות:
    • במקרה הגרוע לוקח זמן הפורפוציונלי לדרגה של הקודקוד ממנו נבדוק.
    • במקרה הגרוע ביותר $\mathrm{\Theta }(V)$.
    • אם נשמור שדה גודל לכל רשימה, או אם נתקדם בו-זמנית בשתי הרשימות (של שני הקודקודים), נוכל לענות על בדיקת שכנות בזמן שהוא פרופוציונלי לדרגה הקטנה מבין השניים.
• מטריצת שכנויות (Adjacency matrix):
  • 
  • מטריצה A בגודל V x V הבנויה מביטים, שבה הערך בתא A(i)(j) הוא 1 אם יש מלע בין קודקוד i ל j ואחרת 0.
  • בגרף לא מכוון, המטריצה תהיה תמיד סימטרית סביב האלכסון הראשי.
  • סיבוכיות מקום - $\mathrm{\Theta }(V^2)$:
    • דורש נפח זיכרון קבוע ביחס למספר הקודקודים, ללא קשר להאם הגרף עמוס או דליל.
  • בדיקת שכנות:
    • זמן קבוע $\mathrm{\Theta }(1)$ מכיוון שזו גישה ישירה לאינדקס במטריצה.
  • זמן מציאת כל השכנים של קודקוד:
    • לוקח $\mathrm{\Theta }(V)$ מכיוון שחוובה לעבור על כל השורה במטריצה כדי לראות אילו ביטים דולקים, גם אם יש לקודקוד מעט שכנים.

סריקה לרוחב - Breadth-First Search (BFS):

• סריקה זו משמשת לאיתור מסלולים ולמציאת המסלול הקצר ביותר מקודקוד מקור S לכל שאר הקודקודים בגרף אליהם ניתן להגיע.
• אופן הפעולה:
  • האלגוריתם סורק את הגרף בצורה הדרגתית, רמה אחר רמה - תחילה כל הקודקודים במרחק 1 מ - S, לאחר מכן הקודקודים במרחק 2 (שהם השכנים של הקודקודים במרחק 1 שלא ביקרנו בהם עדיין), וכן הלאה.
• מבנה הנתונים:
  • האלגוריתם מנהל מבנה נתונים מסוג תור.
  • תחילה נכנס קודקוד המקור אל התור, ובכל איטרציה שולפים קודקוד, בודקים את כל שכניו, וכל שכן שטרם ביקרנו בו מקבל עדכון ונכנס אל סוף התור.
• שלבי הסריקה:
  • בכל שלב בסריקה, נשמרים עבור כל קודקוד שלושה שדות מרכזיים:
    • צבע:
      • מסמן את סטטוס הביקור.
      • לבן: טרם ביקרנו.
      • אפור: הקודקוד נכנס לתור אבל טרם סיימנו לעבור על כל שכניו.
      • שחור: הקודקוד סיים את הטיפול בו (יצא מהתור ועברנו על כל שכניו).
    • מרחק:
      • שומר את כמות הצעדים המינימלית מקודקוד המקור, בתחילת הסריקה מאותחל לאינסוף עבור כל קודקוד שאינו S ו - 0 עבור S.
    • אבא:
      • שומר את הקודקוד דרכו הגענו (מי שהכניס אותנו לתור).
      • שדה זה מאפשר לשחזר בדיעבד את המסלול הקצר ביותר.
• שחזור מסלול:
  • לאחר סיום ריצת ה - BFS, אם נרצה למצוא את המסלול הקצר מ - S לקודקוד V, נלך מ-V לאביו דרך שדה האב שלו, ונמשיך בצורה איטרטיבית עד שנגיע ל - S.
  • ניתן לעשות זאת באמצעות מחסנית רקורסיבית או באמצעות מחסנית מפורשת.
• עץ BFS:
  • אוסף כל הצלעות שנוצרו על ידי שדות האבא אשר יוצרוות מבנה של עץ חסר מעגלים, שמכיל את המסלולים הקצרים ביותר מקודקוד המקור S.
• סיבוכיות הזמן:
  • אם הגרף מיוצג כרשימת שכנויות, סיבוכיות הריצה היא $\mathrm{\Theta }(V+E)$.
    • שלב האתחול לוקח $\mathrm{\Theta }(V)$ , ובמהלך הריצה כל קודקוד נכנס ויוצא מהתור רק פעם אחת.
    • בנוסף אנו סורקים את כל הצלעות של השכנים פעם אחת (בגרף מכוון) או פעמיים (בגרף לא מכוון), ולכן מתווסף עוד $\mathrm{\Theta }(E)$.
  • אם הגרף מיוצג כמטריצת שכנויות, הזמן היה $\mathrm{\Theta }(V^2)$ שכן כדי למצוא את השכנים של קודקוד בתור עלינו לסרוק את כל השורה שלו במטריצה.

סריקה לעומק - Depth-First Search (DFS):

• בסריקה זו הולכים במסלול מסוים הכי עמוק שאפשר, עד שנתקעים. ברגע שנתקעים מבצעים חזרה לאחור אל צומת ההחלטה הקודם שממנו היו עוד אפשרויות ללכת אליהן, וממשיכים משם.

• ההבדלים ביחס ל - BFS:

  • המסלול שיימצא הוא לא בהכרח המסלול הקצר ביותר.
  • חיסכון בזיכרון מכיוון שלא צריך לשמור את כל המצבים האפשריים בכל שלב אלא רק את צומת ההחלטה במסלול הספציפי שבו אנחנו צועדים כרגע.
  • שימוש בגישה רקורסיבית בניגוד לתור.

• משתנה גלובלי time:

  • האלגוריתם מתחזק מונה "זמן" גלובלי, ושומר עבור כל קודקוד u שני חותמות זמן מרכזיות:
    • זמן גילוי ($u.d$): מתי ביקרנו בקודקוד לראשונה והוא נצבע באפור.
    • זמן סיום ($u.f$): מתי סיימנו לסרוק את כל השכנים (והצאצאים) של הקודקוד והוא נצבע בשחור.

• אופן הפעולה:

  • אם הקודקוד לבן, צובעים אותו באפור, מעדכנים את זמן הגילוי שלו, ואז קוראים מתוכו חזרה (רקורסיבית) לפונקציה DFS-visit עבור כל שכניו הלבנים.
  • כשמסיימים לעבור על כל השכנים, צובעים את הקודקוד בשחור ומעדכנים את זמן הסיום שלו.
  • כדי לוודא שכל קודקודי הגרף ייסרקו גם אם הגרף לא קשיר, קיימת פונקציית מעטפת שעוברת על כל הקודקודים בגרף. אם היא נתקלת בקודקוד לבן, היא מתחילה ממנו סריקת DFS-visit מחדש.
  • 

• יער DFS:

  • בדומה לעץ ה-BFS, אוסף הצלעות שנוצרות מהקשרים של אב לבן ($v.\pi$) במהלך הסריקה מרכיב את יער ה - DFS.

• סיבוכיות זמן:

  • במקרה של ייצוג בעזרת רשימת שכנויות, סריקת DFS רצה בזמן של $\mathrm{\Theta }(V+E)$, בדומה ל-BFS.

• משפטים מרכזיים ב-DFS:

  • משפט הסוגריים (Parenthesis theorem):
    • קובע כי קודקוד $v$ יהיה צאצא של קודקוד $u$ ביער ה-DFS אם ורק אם טווח הזמן של $v$ מוכל לחלוטין בתוך טווח הזמן של $u$ (כלומר, $[v.d,v.f]\subseteq [u.d,u.f]$).
    • לחלופין, אם אין ביניהם שום קשר של אב וצאצא ביער, טווחי הזמן שלהם יהיו זרים לחלוטין.
    • 
  • משפט המסלול הלבן (White path theorem):
    • קודקוד $v$ הוא צאצא של $u$ ביער ה-DFS אם ורק אם ברגע שבו הקודקוד $u$ מתגלה (זמן $u.d$), ישנו מסלול בגרף מ-$u$ ל-$v$ שמורכב כולו מקודקודים לבנים בלבד.

• סיווג צלעות בגרף בעזרת DFS:

  • לאחר (או במהלך) סריקת DFS על גרף מכוון, נוכל לסווג כל צלע $(u,v)$ לאחת מ-4 קבוצות:
    1. צלעות עץ (Tree edges): הצלעות של יער ה-DFS עצמו. אלו הצלעות שדרכן גילינו קודקודים חדשים (מזוהות כאשר השכן $v$ הוא לבן).
    2. צלעות אחוריות (Back edges): צלעות המצביעות אל קודקוד שהיה קדמון שלנו ביער, או אל הקודקוד עצמו (מזוהות כאשר השכן $v$ הוא אפור).
    3. צלעות קדימה (Forward edges): צלעות המצביעות מ-$u$ אל הצאצא $v$ שלו, אך לא בדרך הישירה של העץ (מזוהות כאשר השכן $v$ הוא שחור, ותנאי הזמן הוא $u.d<v.d$).
    4. צלעות חוצות (Cross edges): כל שאר הצלעות, אשר בדרך כלל מחברות בין ענפים או עצים נפרדים (מזוהות כאשר השכן $v$ הוא שחור, ותנאי הזמן הוא $u.d>v.d$).
  • הערה על גרף לא מכוון: בגרף לא מכוון לא קיימות צלעות קדימה או צלעות חוצות, כל הצלעות מסווגות או כצלעות עץ או כצלעות אחוריות.

גילוי מעגלים ומיון טופולוגי:

• זיהוי מעגלים:
  • גרף מכוון נחשב "גרף ללא מעגלים" (DAG) אם ורק אם סריקת DFS עליו לא גילתה אף צלע אחורית (Back edge).
  • מציאת צלע אחורית מעידה בהכרח על קיום מעגל בגרף.
• מיון טופולוגי (Topological Sort):
  • ניתן לבצע על גרף מכוון חסר מעגלים (DAG).
  • זהו סידור לינארי של הקודקודים כך שעבור כל צלע מ-$u$ ל-$v$, תמיד $u$ יופיע ברשימה לפני $v$. משמש למידול תלויות (לדוגמה, אילו בגדים חייבים ללבוש לפני בגדים אחרים).
  • האלגוריתם:
    • מריצים סריקת DFS על הגרף. בכל פעם שקודקוד מסיים את הטיפול בו (נצבע בשחור), מכניסים אותו לחלק הקדמי של רשימה מקושרת.
    • הרשימה הסופית שמתקבלת היא המיון הטופולוגי.

תובנות מהתרגול:

• קודקוד super-sink:
  • קודקוד יקרא super-sink אם דרגת היציאה שלו היא 0, ודרגת הכניסה שלו v| -1|.
  • בגרף יכול להיות רק קודקוד אחד כזה.
  • נוכחות של קודקוד מסוג זה תעיד על שורת אפסים וטור של אחדים (פרט למפגש של הקודקוד עם עצמו).
• מיון טופולוגי:
  • ישנם מספר מימושים שונים למיון טופולוגי, ויתכנו מספר מיונים טופולוגים לאותו הגרף)